// 08-图7 公路村村通
// Kruskal 算法实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Set =============================================*/
#define SetElementType int

typedef int SetName; // 集合名称 = 根节点下标
typedef SetElementType *SetType;

SetType createSet(int capacity) {
    SetType set = calloc(capacity, sizeof(SetElementType));
    memset(set, -1, sizeof(SetElementType)*capacity);
    return set;
}

void freeSet(SetType set) {
    free(set);
}

SetName findSet(SetType s, SetElementType x) {
    // 路径压缩
    if (s[x] < 0) {
        return x;
    } else {
        // 先找到根
        // 把根设为x的父节点
        // 再返回根
        return s[x] = findSet(s, s[x]);
    }

}

void unionSet(SetType s, SetName root1, SetName root2) {
    // 按树的规模归并
    if (s[root2] < s[root1]) {
        // root2 节点多, root1挂在root2上，在root2上加上root1的节点
        s[root2] += s[root1]; 
        s[root1] = root2;
    } else {
        // root1 节点多, root2挂在root1上
        s[root1] += s[root2]; 
        s[root2] = root1;
    }
}

/* Array ==========================================*/
void print2D(int **m, int n, int defaultWeight) {
    for (int i=-1; i<n; i++) {
        printf("[%3d]", i);
    }
    printf("\n");
    for (int i=0; i<n; i++) {
        printf("[%3d]", i);
        for (int j=0; j<n; j++) {
            if (m[i][j] == defaultWeight) {
                printf("    -");
            } else {
                printf("%5d", m[i][j]);
            }
        }
        printf("\n");
    }
}

void free2D(int **a, int n) {
    for (int i=0; i<n; i++) {
        free(a[i]);
    }
    free(a);
}

/* MGraph ==========================================*/
// 定义权重的最大值
#define MaxWeight 0x7FFF
// 无路径
#define Connectionless -1
// 有向图, 无向图
#define DirectedGraph 1
#define UndirectedGraph 0

// 权重类型
typedef int WeightType;
typedef struct Edge Edge;
struct Edge {
    int v, w;
    WeightType weight;
};

typedef struct MGraph MGraph;
struct MGraph {
    int directed; // 1-有向图，0-无向图
    int defaultWeight; // 默认的无连接的权重
    int vertexNum; // 顶点数
    int edgeNum;   // 边数
    WeightType **g; // 邻接矩阵
};

Edge createEdge(int v, int w, int weight) {
    Edge e;
    e.v = v;
    e.w = w;
    e.weight = weight;
    return e;
}

MGraph *createGraph(int directed, int defaultWeight, int vertexNum) {
    MGraph* g = (MGraph*)calloc(sizeof(MGraph), 1);
    g->directed = directed;
    g->defaultWeight = defaultWeight;
    g->vertexNum = vertexNum;
    g->edgeNum = 0;
    // 初始化邻接矩阵
    g->g = (WeightType**) malloc(sizeof(WeightType*) * vertexNum);
    for (int v=0; v < g->vertexNum; v++) {
        g->g[v] = (WeightType*) malloc(sizeof(WeightType) * vertexNum);
        for (int w=0; w < g->vertexNum; w++) {
            g->g[v][w] = defaultWeight;
        }
    }
    return g;
}

void freeGraph(MGraph* g) {
    free2D(g->g, g->vertexNum);
    free(g);
}

// 判断图的两个顶点 v1, v2 之间是否有直接连接
int isConnection(MGraph* g, int v1, int v2) {
    return g->g[v1][v2] != g->defaultWeight;
}

void insertEdge(MGraph* g, int v1, int v2, WeightType weight) {
    g->g[v1][v2] = weight;
    if (g->directed == UndirectedGraph) {
        g->g[v2][v1] = weight;
    }
    g->edgeNum++;
}

void printGraph(MGraph* g) {
    printf("Graph n=%d, e=%d\n", g->vertexNum, g->edgeNum);
    print2D(g->g, g->vertexNum, g->defaultWeight);
}

/* Heap ===================================================*/
#define HeapElementType Edge
typedef struct Heap Heap;
struct Heap {
    HeapElementType* data; // 存储元素的数组
    int size; // 元素个数
    int capacity; // 最大容量
    // 堆元素比较器
    int (*comparator)(HeapElementType e1, HeapElementType e2);
};

void percDown(Heap* h, int startIdx) {
    int parent, child;
    // 取出parent结点存放的值
    HeapElementType temp = h->data[startIdx];
    for (parent = startIdx; parent*2+1 < h->size; parent = child) {
        child = parent*2+1;
        if ((child != h->size - 1) && h->comparator(h->data[child], h->data[child+1]) < 0) {
            // 有右儿子，且右儿子比较大
            child++; // 指向右儿子
        }
        if (h->comparator(temp, h->data[child]) >= 0) {
            // 找到了合适位置
            break;
        }
        // 把更大的子节点复制到父节点位置
        h->data[parent] = h->data[child];
    }
    h->data[parent] = temp;
}

Heap* createHeap(int capacity, int (*comparator)(HeapElementType e1, HeapElementType e2)) {
    Heap* h = calloc(1, sizeof(Heap));
    h->data = calloc(capacity, sizeof(HeapElementType));
    h->size = 0;
    h->capacity = capacity;
    h->comparator = comparator;
    return h;
}

// 从已知数组中创建堆，创建堆时把数组 data 调整为堆
Heap* createHeapFromData(HeapElementType* data, int size, int capacity, int (*comparator)(HeapElementType e1, HeapElementType e2)) {
    Heap* h = calloc(1, sizeof(Heap));
    h->data = data;
    h->size = size;
    h->capacity = capacity;
    h->comparator = comparator;
    for (int sidx=(size-1)/2; sidx >= 0; sidx--) {
        percDown(h, sidx);
    }
    return h;
}

void freeHeap(Heap* h) {
    free(h->data);
    free(h);
}

int isFullHeap(Heap* h) {
    return h->size+1 > h->capacity;
}

int isEmptyHeap(Heap* h) {
    return h->size < 1;
}

void insertHeap(Heap* h, HeapElementType item) {
    if (isFullHeap(h)) {
        printf("Heap Full");
        return;
    }
    int i = h->size++;
    // 调整:比较item，与item的父节点（父节点下标=(i-1)/2），若大于父节点，把父节点往下移动
    for (; i > 0 && h->comparator(item, h->data[(i-1)/2]) > 0; i=(i-1)/2) {
        h->data[i] = h->data[(i-1)/2];
    }
    h->data[i] = item;
}

HeapElementType deleteHeap(Heap *h) {
    if (isEmptyHeap(h)) {
        printf("Heap Empty\n");
        HeapElementType error;
        return error;
    }
    // 取出最大的节点
    HeapElementType maxItem = h->data[0];
    // 先把最后一个节点放入第0个节点位置
    h->data[0] = h->data[--h->size];
    percDown(h, 0);
    return maxItem;
}

/* MGraph Kruskal ============================================*/
int checkCycle(SetType vSet, int v1, int v2) { 
    /* 检查连接V1和V2的边是否在现有的最小生成树子集中构成回路 */
    int root1 = findSet(vSet, v1); /* 得到V1所属的连通集名称 */
    int root2 = findSet(vSet, v2); /* 得到V2所属的连通集名称 */
    if (root1 == root2) {
         /* 若V1和V2已经连通，则该边不能要 */
        return 0;
    } else { /* 否则该边可以被收集，同时将V1和V2并入同一连通集 */
        unionSet(vSet, root1, root2);
        return 1;
    }
}

int edgeComparator(Edge e1, Edge e2) {
    if (e1.weight > e2.weight) {
        return -1;
    } else if (e1.weight < e2.weight) {
        return 1;
    }
    return 0;
}

// 把图的边构建为堆
Heap *buildEdgeHeap(MGraph* graph) {
    Edge* es = calloc(graph->edgeNum, sizeof(Edge));
    int eidx = 0;
    for (int v = 0; v < graph->vertexNum; v++) {
        for (int w = v+1; w < graph->vertexNum; w++) {
            if (isConnection(graph, v, w)) {
                es[eidx++] = createEdge(v, w, graph->g[v][w]);
            }
        }
    }
    Heap* heap = createHeapFromData(es, graph->edgeNum, graph->edgeNum, edgeComparator);
    return heap;
}

// Heap *buildEdgeHeap(MGraph* graph) {
//     Heap* heap = createHeap(graph->edgeNum, edgeComparator);
//     for (int v = 0; v < graph->vertexNum; v++) {
//         for (int w = v+1; w < graph->vertexNum; w++) {
//             if (isConnection(graph, v, w)) {
//                 Edge e = createEdge(v, w, graph->g[v][w]);
//                 insertHeap(heap, e);
//             }
//         }
//     }
//     return heap;
// }
/* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */
WeightType Kruskal(MGraph* graph, MGraph* MST) {
    // 权重和
    WeightType totalWeight = 0;
    // 收录的边数
    int edgeCount = 0; 
    // 边权重小顶堆
    Heap* edgeHeap = buildEdgeHeap(graph);
    // 顶点集合
    SetType vertexSet = createSet(graph->vertexNum);
    while (edgeCount < graph->vertexNum-1 && !isEmptyHeap(edgeHeap)) {
        // 获取权重最小的边
        Edge e = deleteHeap(edgeHeap);
        // printf("next edge: %d-%d %d\n", e.v, e.w, e.weight);
        // 如果该边的加入不构成回路，即两端结点不属于同一连通集
        if (checkCycle(vertexSet, e.v, e.w)) {
            /* 将该边插入MST */
            insertEdge(MST, e.v, e.w, e.weight);
            totalWeight += e.weight;
            edgeCount++;
        }
    }
    if (edgeCount < graph->vertexNum-1) {
        // 设置错误标记，表示生成树不存在
        totalWeight = -1;
    }
    freeSet(vertexSet);
    freeHeap(edgeHeap);
    return totalWeight;
}

/* MGraph-input.c ======================================= */
void readEdgeV1WithWeight(MGraph* g, int edgeNum) {
    for (int i=0; i<edgeNum; i++) {
        int v1, v2;
        WeightType dist;
        scanf("%d %d %d", &v1, &v2, &dist);
        insertEdge(g, --v1, --v2, dist);
    }
    g->edgeNum = edgeNum;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    MGraph* g = createGraph(UndirectedGraph, MaxWeight, n);
    readEdgeV1WithWeight(g, m);
    // printGraph(g);

    MGraph* mst = createGraph(UndirectedGraph, MaxWeight, g->vertexNum);
    int totalWeight = Kruskal(g, mst);
    printf("%d\n", totalWeight);
    // printf("mst\n");
    // printGraph(mst);

    freeGraph(g);
    freeGraph(mst);
    return 0;
}
